%       (boy,rabbit,dog,carrot)
%state: where is the boy,rabbit,dog and the carrot? they can be in one or two states, 0 or 1 (side one or two). 
%states: (0,0,0,0),(1,0,0,0), ...
%goal state: (1,1,1,1)
%illegal states: 
% dog and rabbit alone: (0,1,1,-) and (1,0,0,-).
% rabit and carrot alone: (0,1,-,1) and (1,0,-,0).
%relation between state and action: transition(State,Action,ResultingState)
transition([0,0,0,0],[1,1,0,0],[1,1,0,0]).
transition([0,0,0,1],[1,1,0,0],[1,1,0,1]).
transition([0,0,0,1],[1,0,1,0],[1,0,1,1]).
transition([0,0,1,0],[1,1,0,0],[1,1,1,0]).
transition([0,0,1,0],[1,0,0,1],[1,0,1,1]).
transition([0,0,1,1],[1,1,0,0],[1,1,1,1]).
transition([0,0,1,1],[1,0,0,0],[1,0,1,1]).
transition([0,1,0,0],[1,0,1,0],[1,1,1,0]).
transition([0,1,0,0],[1,0,0,1],[1,1,0,1]).
transition([0,1,0,0],[1,0,0,0],[1,1,0,0]).
transition([1,1,1,1],[1,1,0,0],[0,0,1,1]).
transition([1,1,1,0],[1,1,0,0],[0,0,1,0]).
transition([1,1,1,0],[1,0,1,0],[0,1,0,0]).
transition([1,1,0,1],[1,1,0,0],[0,0,0,1]).
transition([1,1,0,1],[1,0,0,1],[0,1,0,0]).
transition([1,1,0,0],[1,0,0,0],[0,1,0,0]).
transition([1,1,0,0],[1,1,0,0],[0,0,0,0]).
transition([1,0,1,1],[1,0,0,0],[0,0,1,1]).
transition([1,0,1,1],[1,0,1,0],[0,0,0,1]).
transition([1,0,1,1],[1,0,0,1],[0,0,1,0]).

stateTransition(S1,_,S1).
stateTransition(S1,[H|T],S2) :-
transition(S1,H,S3),stateTransition(S3,T,S2).

%query: length(X,7) , stateTransition([0,0,0,0],X,[1,1,1,1]). Use this to find the two answers!



%not used:
%action(1,0,0,0).
%action(1,1,0,0). 
%action(1,0,1,0). 
%action(1,0,0,1).
%item(_,d).
%transition(S,A,T) :- state(S),state(T),A+S mod 2 = T ????  (two things: compute A+S mod 2 - and - check equality of the lists.)
%transition(S,A,T) :- transition(S,B,Y),transition(Y,C,T).
%modulus(A,B,C) :- C is A mod B. 
%add two lists:

%sumLists([],[],[]).
%sumLists([H1|T1],[H2|T2],[H3|T3]) :- H3 is (H2+H1) mod 2,sumLists(T1,T2,T3).

%legalTransition([H1|T1],[H2|T2]) :- 1 is (H2+H1) mod 2,
%	sumLists(T1,T2,R),
%	sumList(R,1).  %there is another issue with this method..only thos bits that are the same as boy can flip.
%sumList([],0).
%sumList([H|T],N) :- X is N-H, sumList(T,X).

%transition(S,A,T) :- not(illegalState(S)),
%	not(illegalState(T)),
%	legalTransition(S,A).
%transition(S,A,T)
%	legalTransition(S,T).
%	resState(S,A,T).
	
%stateChange(S1,S2) :- transition(S1,A,S2).
%stateTransition(S1,S2) :- stateChange(S1,S2).
%stateTransition(S1,S2) :- stateChange(S1,Z),
%	                  stateTransition(Z,S2).
%query: stateTransition([0,0,0,0],[1,1,1,1]).

illegalState([0,1,1,0]). 
illegalState([0,1,1,1]). 
illegalState([1,0,0,0]). 
illegalState([1,0,0,1]). 
illegalState([0,1,0,1]). 
illegalState([0,1,1,1]). 
illegalState([1,0,0,0]). 
illegalState([1,0,1,0]).
 
legalState([0,0,0,0]). 
legalState([0,0,0,1]).
legalState([0,0,1,0]).
legalState([0,0,1,1]).
legalState([0,1,0,0]).
legalState([1,1,1,1]).
legalState([1,1,1,0]).
legalState([1,1,0,1]).
legalState([1,1,0,0]).
legalState([1,0,1,1]).

%these are not used!
legalTransition([0,0,0,0],[1,1,0,0]).
legalTransition([0,0,0,1],[1,1,0,1]).
legalTransition([0,0,0,1],[1,0,1,1]).
legalTransition([0,0,1,0],[1,1,1,0]).
legalTransition([0,0,1,0],[1,0,1,1]).
legalTransition([0,0,1,1],[1,1,1,1]).
legalTransition([0,0,1,1],[1,0,1,1]).
legalTransition([0,1,0,0],[1,1,1,0]).
legalTransition([0,1,0,0],[1,1,0,1]).
legalTransition([0,1,0,0],[1,1,0,0]).
legalTransition([1,1,1,1],[0,0,1,1]).
legalTransition([1,1,1,0],[0,0,1,0]).
legalTransition([1,1,1,0],[0,1,0,0]).
legalTransition([1,1,0,1],[0,0,0,1]).
legalTransition([1,1,0,1],[0,1,0,0]).
legalTransition([1,1,0,0],[0,1,0,0]).
legalTransition([1,1,0,0],[0,0,0,0]).
legalTransition([1,0,1,1],[0,0,1,1]).
legalTransition([1,0,1,1],[0,0,0,1]).
legalTransition([1,0,1,1],[0,0,1,0]).
%legal transitions: 
% flip first bit, and one (or none) of the other bits (avoiding illegal transitions):
% e.g. (0,0,0,0) -> (1,1,0,0). 
%transition(S,A,T) S is start state, A is Action (go alone, or carry an item), T is target state.
%Action is number between 1-4 (boy, rabbit, dog, carrot)